并发控制与事务

第 7 篇

这是一份基于 CMU Database Group 课程（Lecture 17-20）关于**事务与并发控制（Transactions & Concurrency Control）**的完整预习与复习课件。

这份课件涵盖了从基础理论（ACID）到具体协议（2PL, OCC），再到现代数据库主流实现（MVCC）的核心内容。

CMU 数据库系统导论：事务与并发控制#

适用对象：数据库系统初学者、进阶开发者 核心目标：理解数据库如何保证数据在并发环境下的安全与一致性。

第一章：并发控制理论基础 (Concurrency Control Theory)#

来源 Lecture 17

1. 核心概念解释#

事务 (Transaction)：
- 定义：事务是数据库管理系统（DBMS）中执行的一系列操作序列（读/写），被视为一个单一的逻辑工作单元。
- ACID 特性：
  - Atomicity (原子性)：事务要么全部执行，要么全部不执行（All or Nothing）。如果事务中途失败，必须回滚（Abort）。
  - Consistency (一致性)：事务必须使数据库从一个一致性状态变换到另一个一致性状态（例如：转账前后总金额不变）。这是应用层的责任，DBMS 负责辅助检查。
  - Isolation (隔离性)：并发执行的事务之间互不干扰，如同它们是串行执行的一样。
  - Durability (持久性)：一旦事务提交，其改变就是永久的，即使系统崩溃也能恢复。
调度 (Schedule)：
- 一组事务的操作在系统中的执行顺序。
- 串行调度 (Serial Schedule)：事务一个接一个地执行，没有交叉。
- 可串行化 (Serializable)：一个并发调度如果其结果等价于某个串行调度，则称其为可串行化的。这是并发控制追求的正确性标准。

2. 关键结论 / 公式 / 方法#

冲突 (Conflict)：
- 当两个操作满足以下条件时，构成冲突：1. 属于不同事务；2. 操作同一对象；3. 至少有一个是写操作。
冲突可串行化 (Conflict Serializability)：
- 方法：构建优先图 (Dependency Graph / Precedence Graph)。
- 节点：每个事务是一个节点。
- 边：如果事务 $T_i$ 的操作 $O_i$ 与事务 $T_j$ 的操作 $O_j$ 冲突，且 $O_i$ 先于 $O_j$ 执行，则画一条从 $T_i$ 到 $T_j$ 的边。
- 结论：如果优先图中没有环 (Cycle)，则该调度是冲突可串行化的。
并发异常 (Anomalies)：
- 脏读 (Dirty Read / Write-Read Conflict)：读到了未提交事务修改的数据。
- 不可重复读 (Unrepeatable Read / Read-Write Conflict)：同一事务内两次读取同一数据，结果不同（因为被其他事务修改并提交了）。
- 丢失更新 (Lost Update / Write-Write Conflict)：两个事务同时修改同一数据，其中一个的修改覆盖了另一个。

3. 易混点或易错点提示#

View Serializability vs. Conflict Serializability：
- View Serializability 允许更多的调度（包含盲写 Blind Writes 的场景），但很难通过算法高效检测（NP-Complete）。DBMS 实际上使用的是 Conflict Serializability。
逻辑时间 vs. 物理时间：
- 在判断调度正确性时，我们不关心事务物理上的开始时间，只关心它们的操作顺序是否等价于某种逻辑上的串行顺序。

4. 简短复习小结#

本章建立了并发控制的理论基石。记住 ACID 是目标，可串行化是隔离性的标准。通过检查读写冲突和构建无环优先图，我们可以从数学上证明一个调度是安全的。

第二章：两阶段锁协议 (Two-Phase Locking, 2PL)#

来源 Lecture 18

1. 核心概念解释#

锁 (Locks) vs. Latch：
- Latch 是低级原语（类似 Mutex），保护内存数据结构（如 B+树节点），持有时间短，无死锁检测。
- Lock 是逻辑保护（保护数据库内容如 Tuples, Tables），持有时间长（整个事务），需要死锁处理。
锁类型：
- Shared Lock (S)：读锁，共享。
- Exclusive Lock (X)：写锁，互斥。
两阶段锁 (2PL)：
- Phase 1 (Growing)：事务请求锁，可以获得新锁，不能释放锁。
- Phase 2 (Shrinking)：事务释放锁，不能获取新锁。

2. 关键结论 / 公式 / 方法#

Strong Strict 2PL (SS2PL / Rigorous 2PL)：
- 实际系统中最常用的变体。
- 规则：事务直到提交 (Commit) 时才释放所有锁。
- 优点：避免了级联回滚 (Cascading Aborts)，保证了恢复的安全性。
死锁处理 (Deadlock Handling)：
- 检测 (Detection)：维护 Wait-for Graph，发现环后选择一个受害者 (Victim) 回滚。
- 预防 (Prevention)：基于时间戳（优先级）决定等待还是回滚。
  - Wait-Die (Old waits for Young)：老事务等新事务，新事务遇老事务自杀。
  - Wound-Wait (Young waits for Old)：新事务等老事务，老事务抢占新事务（新事务被杀）。
多粒度锁 (Lock Granularity)：
- 为了平衡并发度与开销，引入意向锁 (Intention Locks)：IS, IX, SIX。
- 规则：在锁住子节点（如 Tuple）前，必须先锁住父节点（如 Table）的对应意向锁。例如，写一个 Tuple 前，表上要有 IX 锁。

3. 易混点或易错点提示#

2PL 能够防止脏读吗？
- 标准的 2PL（允许在 Shrinking 阶段释放锁）可能会导致级联回滚，但生成的调度依然是冲突可串行化的。Strong Strict 2PL 才彻底解决了脏读和级联回滚问题。
死锁预防的方向：
- 无论是 Wait-Die 还是 Wound-Wait，核心都是保证等待方向是单向的（例如总是老等新，或者总是新等老），从而避免环的产生。

4. 简短复习小结#

2PL 是一种悲观 (Pessimistic) 协议，假设冲突频繁发生。Strong Strict 2PL 是现代系统的基石。利用意向锁可以在表锁和行锁之间灵活切换。必须处理死锁。

第三章：时间戳排序与乐观并发控制 (OCC)#

来源 Lecture 19

1. 核心概念解释#

乐观并发控制 (Optimistic Concurrency Control, OCC)：
- 假设：冲突很少发生。
- 思路：让事务先执行，不加锁，最后提交时再检查是否冲突。
- 三个阶段：
  1. Read Phase：事务在私有工作区（Private Workspace）执行读写，不修改全局数据库。
  2. Validation Phase：DBMS 检查该事务是否与其他事务冲突。
  3. Write Phase：验证通过后，将私有工作区的修改应用到全局数据库。
时间戳排序 (Timestamp Ordering)：
- 利用时间戳（单调递增）来决定事务的串行化顺序。

2. 关键结论 / 公式 / 方法#

OCC 验证方法：
- Backward Validation（最常用）：检查当前事务读写的数据是否与最近已提交的事务冲突。
- Forward Validation：检查当前事务是否与正在运行的事务冲突。
幻读 (Phantom Read)：
- 现象：同一事务内两次范围查询（Range Scan），由于其他事务插入/删除了数据，导致结果集行数不同。
- 原因：锁机制通常只能锁住存在的行，锁不住“不存在”的间隙。
- 解决方案：
  - Index Locking / Key-Range Locking：利用索引锁住键值之间的“间隙 (Gap)”。
  - Next-Key Locking：锁住当前记录 + 之前的间隙。

3. 易混点或易错点提示#

时间戳分配时机：
- 在 OCC 中，时间戳通常在验证阶段 (Validation Phase) 分配，而不是事务开始时。这能确保证逻辑提交顺序与物理时间顺序更匹配。
隔离级别 (Isolation Levels)：
- 从高到低：Serializable > Repeatable Read > Read Committed > Read Uncommitted。
- 注意：大多数数据库默认级别不是 Serializable，而是 Read Committed 或 Repeatable Read。

4. 简短复习小结#

OCC 适用于低冲突 (Low Contention) 场景（如读取为主），避免了锁的开销。但如果冲突高，事务反复回滚，性能会很差。为了解决幻读，我们需要引入索引锁或间隙锁。

第四章：多版本并发控制 (MVCC)#

来源 Lecture 20

1. 核心概念解释#

多版本并发控制 (MVCC)：
- 核心思想：写操作不覆盖旧数据，而是创建一个新版本。读操作读取旧版本。
- 优势：读写不互斥 (Writers don’t block Readers, Readers don’t block Writers)。只读事务不需要加锁就可以读到一致的快照。
快照隔离 (Snapshot Isolation)：
- 事务看到的数据库状态是其开始那一刻的快照。
- First-Writer Wins：两个事务同时修改同一对象，先提交的成功，后的失败。

2. 关键结论 / 公式 / 方法#

版本存储 (Version Storage)：
- Append-Only (Postgres)：新版本追加到表中，旧版本留原地。需维护版本链。
- Delta Storage (MySQL/Oracle, 最优)：主表存最新版，旧数据以 Delta (Diff) 形式存入回滚段 (Rollback Segment)。
垃圾回收 (Garbage Collection)：
- DBMS 需要识别哪些旧版本对所有活跃事务都不可见（即所有活跃事务的开始时间戳都晚于该版本的结束时间戳），然后回收空间。
写偏斜 (Write Skew)：
- 这是快照隔离 (Snapshot Isolation) 特有的异常。
- 例子：两个事务分别读取所有球的颜色，一个把白球染黑，一个把黑球染白。串行化执行结果是全黑或全白，但快照隔离下可能出现黑白混合。这在传统 2PL 中不会发生。

3. 易混点或易错点提示#

索引管理：
- 在 Append-Only 模式下，每次更新由于生成新物理行，所有索引（包括辅助索引）都需要更新指向新位置，或者使用逻辑指针（Logical Pointer）指向主键，再由主键索引找到物理行（MySQL 的做法）。
MVCC 不是一种独立的协议：
- MVCC 通常与 2PL 或 OCC 结合使用。例如：MySQL (InnoDB) 使用 MVCC 来支持非阻塞读，但写操作依然使用 2PL（行锁）。